package com.lenl.datastruct.tree;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-04 17:14
 * @description 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        //数组进行升序（大顶堆）
        int arr[]={4,6,8,5,9,-1,90,89,32,999};
        //测试堆排序
        heapSort(arr);
    }

    //堆排序方法
    public static void heapSort(int[] arr){
        System.out.println("堆排序！");
        int temp=0;
//        adjustHeap(arr,1,arr.length);
//        System.out.println("第一次"+ Arrays.toString(arr)); //[4, 9, 8, 5, 6]
//        adjustHeap(arr,0,arr.length);
//        System.out.println("第二次"+Arrays.toString(arr)); //[9, 6, 8, 5, 4]
        for (int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        for (int j=arr.length-1;j>0;j--){
            //交换
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }

        //System.out.println(Arrays.toString(arr));
    }
    //将一个数组(二叉树)调整成一个大顶堆

    /**
     * 功能：完成将以i对应的非叶子节点的树调整成大顶堆
     * @param arr 待调整数组
     * @param i 非叶子节点在数组中的索引
     * @param length 调整的数据个数，逐渐减少
     */
    public  static void adjustHeap(int[] arr,int i,int length){
        //先取出当前元素的值保存在临时变量‘
        int temp=arr[i];
        for (int k=i*2+1;k<length;k=k*2+1){
            if(k+1<length&& arr[k]<arr[k+1]){
                //说明左子节点值小于右子节点的值
                k++; //k指向右子节点
            }
            if(arr[k]>temp){
                //子节点大于父节点,将较大值赋给当前节点
                arr[i]=arr[k];
                i=k;
            }else{
                break;
            }
        }
        //for循环结束后已经将以i为父节点的树的最大值放在最顶端
        arr[i]=temp; //将temp值放到调整后的位置

    }
}
